Codeforces Round 905 (Div. 2)

Chemistry

只要奇数字母的个数不大于 \(k+1\) 即可，因为回文串最多有一个奇数字母。

public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    String s = io.next();

    int[] cnt = new int[26];
    for (int i = 0; i < n; i++) {
        cnt[s.charAt(i) - 'a']++;
    }

    int sum = 0;
    for (int x : cnt) {
        if (x % 2 == 1) {
            sum++;
        }
    }
    io.println(sum - 1 > k ? "NO" : "YES");
}

Raspberries

当 \(k=2,3,5\) 时，因为 \(k\) 是质数，如果所有数的乘积能够被 \(k\) 整除，必定存在一个数能够被 \(k\) 整除，所以单独计算每个数即可。当 \(k=4\) 时，需要计算存在一个数能被 \(4\) 整除的最少操作数，还需要计算存在两个能被 \(2\) 整除的数的最少操作数，答案为两者的最小值。

public static void solve() {
    int n = io.nextInt(), k = io.nextInt();

    int cnt = 0;
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
        if (a[i] % 2 == 0) {
            cnt++;
        }
    }

    int ans = k;
    for (int i = 0; i < n; i++) {
        ans = Math.min(ans, (k - a[i] % k) % k);
    }
    if (k == 4) {
        ans = Math.min(ans, Math.max(0, 2 - cnt));
    }
    io.println(ans);
}

You Are So Beautiful

如果某个子数组作为子序列只出现过一次，因为子数组本身就是子序列，所以没有其他方式能够构成该子数组，即子数组的左端点左边没有和它相同的数，右端点的右边也没有和它相同的数。我们可以使用集合 + 前缀和的方式预先计算每个位置及其左边满足条件的左端点个数，然后倒序处理数组，对每个满足条件的右端点，都将其对应的左端点的个数添加到答案。

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }

    Set<Integer> set = new HashSet<>();
    int[] prefix = new int[n + 1];
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + (set.add(a[i]) ? 1 : 0);
    }
    set.clear();

    long ans = 0L;
    for (int i = n - 1; i >= 0; i--) {
        if (set.add(a[i])) {
            ans += prefix[i + 1];
        }
    }
    io.println(ans);
}

Dances (Easy version)

题目真难读，简单版只会在数组 \(a\) 中添加一个 \(1\)，然后计算最少操作数，可以使用排序 + 双指针进行处理。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] a = new int[n];
    a[0] = 1;
    for (int i = 1; i < n; i++) {
        a[i] = io.nextInt();
    }
    int[] b = new int[n];
    for (int i = 0; i < n; i++) {
        b[i] = io.nextInt();
    }

    Arrays.sort(a);
    Arrays.sort(b);

    int k = 0;
    for (int i = 0, j = 0; i < n - k; i++, j++) {
        while (j < n && a[i] >= b[j]) {
            k++;
            j++;
        }
    }
    io.println(k);
}

Dances (Hard Version)

困难版，计算在数组中分别添加 \([1,m]\) 需要的最少操作数。通过观察可以发现（真发现不了），改变 \(a[0]\) 最多只会使操作次数加 \(1\)，所以我们可以二分该边界值，然后计算答案即可。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] a = new int[n];
    for (int i = 1; i < n; i++) {
        a[i] = io.nextInt();
    }
    int[] b = new int[n];
    for (int i = 0; i < n; i++) {
        b[i] = io.nextInt();
    }
    Arrays.sort(b);

    int k = calc(a, b, 1);

    int lo = 1, hi = m;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (calc(a, b, mid) == k) lo = mid + 1;
        else hi = mid - 1;
    }
    io.println((long) m * k + (m - lo + 1));
}

private static int calc(int[] a, int[] b, int x) {
    a[0] = x;
    a = a.clone();
    Arrays.sort(a);

    int n = a.length, k = 0;
    for (int i = 0, j = 0; i < n - k; i++, j++) {
        while (j < n && a[i] >= b[j]) {
            k++;
            j++;
        }
    }
    return k;
}

竟然还有更简单的方法，首先计算 \(a\) 中 \(n-1\) 个数对应 \(b\) 中 \(n\) 个数的最少删除次数，并同时维护 \(b\) 中不满足 \(a[i]<b[j]\) 的最后一个值，该值就是操作次数的分界点，直接计算答案即可。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] a = new int[n];
    a[0] = Integer.MAX_VALUE;
    for (int i = 1; i < n; i++) {
        a[i] = io.nextInt();
    }
    int[] b = new int[n];
    for (int i = 0; i < n; i++) {
        b[i] = io.nextInt();
    }

    Arrays.sort(a);
    Arrays.sort(b);

    int k = 0, val = m + 1;
    for (int i = 0, j = 0; i < n - k; i++, j++) {
        while (j < n && a[i] >= b[j]) {
            val = b[j];
            k++;
            j++;
        }
    }
    io.println((long) m * (k - 1) + Math.max(0, m - val + 1));
}